package com.dataStructures.recursion;

/**
 * 八皇后问题（回溯算法的典型案例）
 * 在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即:任意两个皇后都不能处于同一行、 同一列或同一斜线上，问有多少种摆法(92)。
 */
public class Queue8 {

	int max = 8;
	int[] array = new int[max];
	static int count = 0;
	static int judgeCount = 0;

	public static void main(String[] args) {
		Queue8 queue8 = new Queue8();
		queue8.setQueue(0);
		System.out.printf("一共有 %d 种解法", count);
		System.out.printf("一共判断冲突的次数 %d 次", judgeCount);
	}

	/**
	 * 放置第 n 个皇后（递归）
	 * check 是 每一次递归时，进入到 check 中都有 for(int i = 0; i < max; i++)，因此会有回溯
	 *
	 * @param n 第几个
	 */
	private void setQueue(int n) {
		if (n == max) {
			printLocal();
			return;
		}
		// 依次放入皇后，并判断是否冲突
		// 判断每一列
		for (int i = 0; i < max; i++) {
			array[n] = i;
			if (judge(n)) {
				// 如果不冲突，继续放后一个皇后
				setQueue(n + 1);
			}
			// 如果冲突，就继续执行 array[n] = i; 即将第 n 个皇后，放置在本行的 后移的一个位置
		}

	}

	/**
	 * 判断第 n 个皇后和前边的所有已经摆放的皇后的位置是否冲突
	 *
	 * @param n 第 n 个皇后
	 * @return 是否冲突
	 */
	private boolean judge(int n) {
		judgeCount++;
		for (int i = 0; i < n; i++) {
			// 是否同一列（不用判断是否同一行）
			boolean sameColumn = array[i] == array[n];
			// 是否在同一斜线上（两点的行距等于列距，则在同一斜线上）
			boolean sameDiagonal = Math.abs(n - i) == Math.abs(array[n] - array[i]);
			if (sameColumn || sameDiagonal) {
				return false;
			}
		}
		return true;
	}

	/**
	 * 输出皇后摆放的位置
	 */
	private void printLocal() {
		count++;
		for (int i : array) {
			System.out.print(array[i] + " ");
		}
		System.out.println();
	}
}
